◀ Prev · Parts · Full · Next ▶

• Algorithmic complexity (Chaitin 1969, Schnorr 1973, Levin 1973): Algorithmic complexity (also known as (prefix-free) Kolmogorov complexity or program-size complexity) can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence w a natural number K(w) that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output w when run. The complexity is required to be prefix-free: The program (a sequence of 0 and 1) is followed by an infinite string of 0s, and the length of the program (assuming it halts) includes the number of zeroes to the right of the program that the universal Turing machine reads. The additional requirement is needed because we can choose a length such that the length codes information about the substring. Given a natural number c and a sequence w, we say that w is c-incompressible if K ( w ) ≥ ≥ | w | − − c {\displaystyle K(w)\geq |w|-c} .

An infinite sequence S is Martin-Löf random if and only if there is a constant c such that all of S's finite prefixes are c-incompressible. More succinctly, K ( w ) ≥ ≥ | w | − − O ( 1 ) {\displaystyle K(w)\geq |w|-O(1)} .

◀ Prev · Parts · Full · Next ▶